2-2

Basic Properties of Partitions

Nicholas Wheeler
Reed College Physics
20 February 2008

Mathematica provides a command

PartitionsP[10]

that reports in how many distinct ways a positive integer can be partitioned, and in the Combinatorica package

<<Combinatorica`

provides commands that list them

IntegerPartitions[10]

Length[%]

Built into Mathematica itself (no need to install the Combinatorica package) is a command that selects from such lists all the partitions into not more than k parts

IntegerPartitions[10,3]

and another that lists all the partitions into precisely k parts:

IntegerPartitions[10,{3}]

Two closely related partition functions:

I have developed an interest in the function

p[n_, k_]:=Length[IntegerPartitions[n,{k}]]

that describes the number of ways that n can be partitioned into precisely k parts.

Table[Table[p[n,k], {k,1,n}],{n,1,15}]//TableForm

Specifically, I have interest in the ROWS of the preceding table, in the limit that n is large. From my limited knowledge of the literature I gain the impression that authors are more often interested in properties of the function

P[n_, k_]:=Length[IntegerPartitions[n,k]]

that describes the number of ways that n can be partitioned into not more than k parts.

Table[Table[P[n,k], {k,1,n}],{n,1,15}]//TableForm

Obviously,

PartitionsP[n]=P[n,n]

which I demonstrate:

Table[{n,PartitionsP[n]==P[n,n]}, {n,1,15}]//TableForm

It is obvious also that

P[n,k]==(∑_(j=1)^k)p[n,j]

Table[Table[P[n,k]==(∑_(j=1)^k)p[n,j], {k,1,n}],{n,1,15}]//TableForm

It is obvious that there is only one way—namely, with a string of ones—to partition n into precisely n parts. Thus

Table[{n,IntegerPartitions[n,{n}]}, {n,1,10}]//TableForm

That accounts for the string of 1s that appear on the prinicipal diagonal in the table

Table[Table[p[n,k], {k,1,n}],{n,1,15}]//TableForm

It is equally obvious that there is also only one—namely, with a string of ones and a solitary 2—to partition n into precisely k = n – 1 parts. Thus

Table[{n,IntegerPartitions[n,{n-1}]}, {n,2,10}]//TableForm

which accounts for the string of 1s that appear on the first sub-diagonal. I present now data intended to provide insight into why it is that subsequent sub-diagonals devolve into a series of 2s, then of 3s, then of 5s, then of 7s, then of 11s, etc.

In this list of pairs

Table[{n,IntegerPartitions[n,{n-2}]}, {n,4,10}]//TableForm

3 makes its first appearance, and

PartitionsP[3-1]

In this list of triples

Table[{n,IntegerPartitions[n,{n-3}]}, {n,6,10}]//TableForm

4 makes its first appearance, and

PartitionsP[4-1]

In this list of quintuples

Table[{n,IntegerPartitions[n,{n-4}]}, {n,8,15}]//TableForm

5 makes its first appearance, and

PartitionsP[5-1]

In this list of septuples

Table[{n,IntegerPartitions[n,{n-5}]}, {n,10,15}]//TableForm

6 makes its first apparance, and

PartitionsP[6-1]

Here is a fresh copy of the data

Table[Table[p[n,k], {k,1,n}],{n,1,16}]//TableForm

and here is a sharp indication of the pattern we have been discussing:

Table[p[2+d,1+d],{d,0,10}]
Table[p[4+d,2+d],{d,0,10}]
Table[p[6+d,3+d],{d,0,10}]
Table[p[8+d,4+d],{d,0,10}]
Table[p[10+d,5+d],{d,0,10}]
Table[p[12+d,6+d],{d,0,10}]
Table[p[14+d,7+d],{d,0,10}]
Table[p[16+d,8+d],{d,0,10}]
Table[p[18+d,9+d],{d,0,10}]
Table[p[20+d,10+d],{d,0,10}]

The numbers that appear in such lists (i.e., are repeated entries on sub-diagonals) are precisely the partition numbers:

Table[{n,PartitionsP[n]}, {n,1,10}]//TableForm

Which means—look again to this display

—that every row, beginning with k=Ceiling[(n/2)], presents the leading partition numbers in reverse sequence:

Table[Table[p[n,k]-PartitionsP[n-k],{k,Ceiling[(n/2)],n}],{n,1,10}]//TableForm

and every column begins with such a sequence:

Table[Table[p[n,k]-PartitionsP[n-k],{n,k, Floor[2k]}],{k,1,10}]//TableForm

I turn my attention now to the function P[n, k] and to discussion of its relationship to p[n, k].

Table[Table[P[n,k], {k,1,n}],{n,1,15}]//TableForm

We are, as previously remarked, not surprised to see the partition numbers marching down the diagonal. It is a striking fact that the columns in the preceding table can be obtained by snipping off the tops of the corresponding columns in the following table.

Specifically,

Table[Table[P[n,k]-p[n+k,k], {k,1,n}],{n,1,15}]//TableForm

which means that much (not all!) of the p[n, k] data can be recovered from P[n, k] data. And conversely:

Table[Table[P[m-k,k]-p[m,k], {m, k+1, 16}],{k,1,16}]//TableForm

G. E. Andrewss & K. Ericksson, in Integer Partitions (2004), devote much of their Chapter 6 to the development of formulae such as the following:

Andrews2[n_]:=Floor[(n/2)]+1

Table[{n,P[n,2],Andrews2[n]}, {n,1,10}]//TableForm

Andrews3[n_]:=Round[((((n+3))^2)/12)]

Table[{n,P[n,3],Andrews3[n]}, {n,1,10}]//TableForm

Andrews4A[n_]:=Round[(((n+1)((n^2)+23n+85))/144)-(((n+4))/8)Floor[((n+1)/2)]]

Table[{n,P[n,4],Andrews4A[n]}, {n,1,10}]//TableForm

Andrews & Ericksson give two alternative descriptions of P[n, 4], and also provide

Andrews5[n_]:=Round[(((n+8)((n^3)+22(n^2)+44n +280+180Floor[(n/2)] ))/2880)]

Table[{n,P[n,5],Andrews5[n]}, {n,1,10}]//TableForm

Evidently we should expect such formulae to become more and more Baroque—also more and more difficult to develop—as k increases. It is interesting that we develop a unit disagreement in the neighborhood of n = 100

Table[{n,P[n,5],Andrews5[n]}, {n,100,105}]//TableForm

which by n = 200 has increased to a 2-unit disagreement:

Table[{n,P[n,5],Andrews5[n]}, {n,200,205}]//TableForm